package chapter02;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class InorderTraversal94 {
    /**
     * 非递归中序
     * 准备一个栈stack 当前来到节点node=head
     * while 栈容量不为null或者node!=null
     *    1.node不为null
     *      将后续左孩子加入栈
     *      while node!=null
     *          stack.push(node)
     *          node=node.left
     *    2.node为null
     *      cur=stack.pop() 出栈
     *      处理cur
     *      node=cur.right 循环处理cur右子树
     * -------------------------------------
     * Morris中序遍历 一个节点有左孩子可以访问两次 否则只能访问一次;只能到达一次直接处理 能到达两次第二次处理
     * 当前节点node
     * while node!=null
     *  mostRight=node.left 左孩子
     *  1.如果左子树为空 mostRight==null
     *      node=node.right 来到右子树上
     *  2.如果左子树不为null
     *      while mostRight.right!=null&&mostRight.right!=node 找到左子树上最右节点
     *          mostRight=mostRight.right
     *      a).最右节点的右孩子为null是第一次到达 mostRight.right==null
     *          mostRight.right=node 将最右节点的右孩子指向node
     *          node=node.left 来到左子树上
     *      b).最右节点的右孩子为node是第二次到达 mostRight.right==node
     *          打印处理node
     *          mostRight.right=null 恢复叶子节点
     *          node=node.right 来到右子树上
     */
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
       }
    }

    //Morris中序遍历
    public List<Integer> inorderTraversal(TreeNode root){
        List<Integer> res=new ArrayList<>();
        if(root==null){
            return res;
        }
        TreeNode cur=root;
        while (cur!=null){
            TreeNode mostNode=cur.left;
            if(mostNode==null){
                res.add(cur.val);
                cur=cur.right;
            }else{
                while (mostNode.right!=null&&mostNode.right!=cur){
                    mostNode=mostNode.right;
                }
                if(mostNode.right==null){
                    mostNode.right=cur;
                    cur=cur.left;
                }else{
                    res.add(cur.val);
                    mostNode.right=null;
                    cur=cur.right;
                }
            }
        }
        return res;
    }

    //非递归中序遍历
    public List<Integer> inorderTraversal2(TreeNode root){
        List<Integer> res=new ArrayList<>();
        if(root==null){
            return res;
        }
        Stack<TreeNode> stack=new Stack<>();
        while (!stack.isEmpty()||root!=null){
            if(root!=null){
                stack.push(root);
                root=root.left;
            }else{
                TreeNode node=stack.pop();
                res.add(node.val);
                root=node.right;
            }
        }
        return res;
    }

    //递归中序遍历
    public List<Integer> inorderTraversal1(TreeNode root) {
        List<Integer> res=new ArrayList<>();
        if(root==null){
            return res;
        }
        process(res,root);
        return res;
    }

    public void process(List<Integer> res,TreeNode node){
        if(node==null){
            return;
        }
        process(res,node.left);
        res.add(node.val);
        process(res,node.right);
    }
}
